package leetcode;

/*
693. 交替位二进制数
给定一个正整数，检查他是否为交替位二进制数：换句话说，就是他的二进制数相邻的两个位数永不相等。

示例 1:

输入: 5
输出: True
解释:
5的二进制数是: 101
示例 2:

输入: 7
输出: False
解释:
7的二进制数是: 111
示例 3:

输入: 11
输出: False
解释:
11的二进制数是: 1011
 示例 4:

输入: 10
输出: True
解释:
10的二进制数是: 1010
*/

public class problems_968 {
    public static void main(String[] args) {
        TreeNode A1 = new TreeNode(1);
        TreeNode A2 = new TreeNode(2);
        TreeNode A3 = new TreeNode(3);
        TreeNode A4 = new TreeNode(5);
        A1.left = A2;
        A1.right = A3;
        A2.left = A4;
        System.out.println(new Solution().minCameraCover(A1));
    }

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    static class Solution {
        int ret = 0; // 最终结果
        public int minCameraCover(TreeNode root) {
            // 对根节点进行处理
            if (dfs(root) == 0) {
                // 如果最后根节点是待处理节点，则根节点安装
                ret++;
            }
            return ret;
        }
        // 使用dfs从下往上进行处理
        // 0=>这个结点待覆盖
        // 1=>这个结点已经覆盖
        // 2=>这个结点上安装了相机
        private int dfs(TreeNode node) {
            // 空节点，相当于已经处理
            if (node == null) {
                return 1;
            }
            // dfs遍历
            int left = dfs(node.left);
            int right = dfs(node.right);
            // 左右点都是未覆盖，则只有在此节点上安装
            if (left == 0 || right == 0) {
                ret++;
                return 2;
            }
            // 左右都覆盖，此阶段留待上一节点覆盖
            if (left == 1 && right == 1) {
                return 0;
            }
            // 左右任意安装，则此阶段覆盖
            if (left + right >= 3) {
                return 1;
            }
            return -1;
        }
    }
}